package cn.jietuo.first.class01;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2020/5/26
 * @description:
 * 在一个有序数组中，找某个数是否存在
 * 可以使用二分查找的方法来实现
 */
public class Code04_BSExist {

    public static boolean bsExist(int[] arr, int i) {
        int l = 0;
        int r = arr.length -1;
        int mid = 0;
        while (l < r){
            // mid = (L + R)/2
            // 如果L 10亿 R 18亿 上面的表达式就会越界
            // mid = L + (R - L)/2
            // N/2  -->  N >> 1
            mid = ((r-l) >> 1) + l;
            if (arr[mid] == i){
                return true;
            }else if(arr[mid] > i){
                r = mid -1;
            }else{
                l = mid + 1;
            }
        }
        return arr[l] == i;
    }

    public static void main(String[] args) {
        int[] array = new int[]{1,3,6,8,9,29,122,234};
        boolean b = bsExist(array, 6);
        System.out.println(b);
    }
}
